package 链表;

import sun.awt.SunHints;

import java.util.HashSet;
import java.util.Set;

public class Solution6 {
    //https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
    public ListNode FindFirstCommonNode1(ListNode pHead1, ListNode pHead2) {
        //思路1：快慢指针，先走几步，然后同时走相遇
        int count1 = 0, count2 = 0;
        ListNode cur1 = pHead1, cur2 = pHead2;
        while (cur1 != null) {
            count1++;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            count2++;
            cur2 = cur2.next;
        }
        cur1 = pHead1;
        cur2 = pHead2;
        int count = count1 - count2;
        if(count > 0) {
            while (count != 0) {
                cur1 = cur1.next;
                count--;
            }
        }else {
            count = - count;
            while (count != 0) {
                cur2 = cur2.next;
                count--;
            }
        }
        while (cur1 != null && cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        //思路2：扔进用数据结构判重复
        Set<ListNode> set = new HashSet<>();
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while (cur1 != null) {
            set.add(cur1);
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            if(set.contains(cur2)) {
                return cur2;
            }
            cur2 = cur2.next;
        }
        return null;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //题解：3 + 2 = 2 + 3，走完最后一定会相遇
        if(pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        //{1,2,3,4,5},{},{6,7,8} —> 意思是phead2在6节点上，如果是下面的 为空先存 然后连续跳的话，就错过了相遇点6而延迟相遇到了7
        while (cur1 != cur2) {
            /*if(cur1 == null) {
                cur1 = pHead2;
            }
            if(cur2 == null) {
                cur2 = pHead1;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;*/
            if(cur1.next == null && cur2.next == null) {
                return null;
            }
            if(cur1.next == null) {
                cur1 = pHead2;
            }else {
                cur1 = cur1.next;
            }
            if(cur2.next == null) {
                cur2 = pHead1;
            }else {
                cur2 = cur2.next;
            }
        }
        return cur1;
    }
}
